from typing import List
from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(0, len(nums)):
            ans ^= nums[i]
        return ans
    def singleNumber2(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)



'''
复杂度分析
时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
空间复杂度：O(1)。
'''

'''

假设 nums = [a, b, c, d]，那么 reduce(lambda x, y: x ^ y, nums) 
会按照如下方式计算：
reduce(lambda x, y: x ^ y, nums)
     step1: result = a ^ b
     step2: result = result ^ c
     step3: result = result ^ d
     
'''
print(Solution().singleNumber2([2,2,1]))